package org.example.leetcode;

/**
 * @version 1.0.0
 * @author: lynn
 * @description:  实现 strStr()
 * @date: 2021/7/27 12:49
 */
public class LC28 {
    public static void main(String[] args) {
        LC28 lc=new LC28();
        System.out.println(lc.strStr("mississippi","issip"));
    }
    //fixme kmp算法  https://www.bilibili.com/video/BV15k4y1177M?from=search&seid=3980767625723955695
    //fixme 浙江大学 kmp算法 https://www.bilibili.com/video/BV1Kb41127fT?p=145
    //如果是常规查找，那么算法复杂度 O(m*n),kmp算法复杂度 o(m+n),kmp是模式匹配算法
    //match数组是最长子串结尾的位置表，是一个数组
    // 特点 1.算法复杂度 o(m+n) 2. int[] match 只跟 pattern有关系 3. text只遍历一遍，保证线性
    public int strStr(String haystack, String needle) {

         int n=haystack.length();
         int m=needle.length();
         if (m==0) return 0;
         if (n==0) return -1;
        return KMP(haystack.toCharArray(),needle.toCharArray());
    }
    public int KMP(char[] text,char[] pattern){
        int m=pattern.length;
        int[] match=buildMatch(pattern);
        int s=0;int p=0;
        while (s < text.length && p < pattern.length) {
            if (text[s]==pattern[p]){
                s++;
                p++;
            }else {
                if (p==0){
                    s++;
                }else{
                    p=match[p-1]+1;
                }
            }
        }
        return p==m?(s-m):-1;
    }

    public int[] buildMatch(char[] pattern){
        int m=pattern.length;
        int[] match=new int[m];
        match[0]=-1;
        int pre;
        for (int j=1;j<m;j++){
            pre=match[j-1];
            while (pre>=0 && pattern[pre+1]!=pattern[j]){
                pre=match[pre];
            }
            if (pattern[pre+1]==pattern[j]){
                match[j]=pre+1;
            }else{
                match[j]=-1;
            }
        }

        return match;
    }
}
